package com.yww.leetcode2.string;

/**
 * @author yww
 * @description 151. 反转字符串中的单词
 * @since 2024/11/19
 */
public class ReverseWords151_03 {
    // 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
    // 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
    // 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
    // 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。
    // 返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
    public String reverseWords(String s) {
        s = removeExtraSpaces(s);
        char[] charArray = s.toCharArray();
        reverse(charArray, 0, charArray.length - 1);
        // 针对每个单词进行反转
        int begin = 0, end = 0;
        while (end < charArray.length) {
            if (charArray[end] != ' ' && end < charArray.length - 1) {
                end++;
                continue;
            }
            if (!(end < charArray.length - 1)) {
                reverse(charArray, begin, end);
            } else {
                reverse(charArray, begin, end - 1);
            }

            begin = ++end;
        }

        return new String(charArray);
    }

    public static String removeExtraSpaces(String s) {
        int fast = 0;
        boolean need = false;
        StringBuilder sb = new StringBuilder();
        for (; fast < s.length(); fast++) {
            if (s.charAt(fast) != ' ') {
                sb.append(s.charAt(fast));
                need = true;
                continue;
            }
            if (need) {
                sb.append(' ');
                need = false;
            }
        }
        return sb.charAt(sb.length() - 1) == ' ' ? sb.substring(0, sb.length() - 1) : sb.substring(0, sb.length());
    }

    public static void reverse(char[] charArr, int begin, int end) {
        while (begin < end) {
            char temp = charArr[begin];
            charArr[begin++] = charArr[end];
            charArr[end--] = temp;
        }
    }


    public static void main(String[] args) {
        String s = new ReverseWords151_03().reverseWords("Hello World");
        System.out.println(s);

    }
}
